package _021_10_19

import "strconv"

const (
	Get = 2
	Set = 1
)

type LruNode struct {
	Next  *LruNode
	Pre   *LruNode
	Key   string
	Value int
}

type Lru struct {
	k    int
	lru  map[string]*LruNode
	head *LruNode
	cur  *LruNode
}

func (this *Lru) Get(params []int) int {
	node, ok := this.lru[strconv.Itoa(params[1])]
	if !ok {
		return -1
	}
	next := node.Next
	pre := node.Pre

	if this.cur != node {
		pre.Next = next
		next.Pre = pre
		node.Pre = this.cur
		this.cur.Next = node
		node.Next = nil
		this.cur = this.cur.Next
	}
	return node.Value
}

func (this *Lru) Set(param []int) {
	if this.k == len(this.lru) {
		this.Del()
	}
	node := &LruNode{}
	node.Next = nil
	node.Pre = this.cur
	node.Value = param[2]
	node.Key = strconv.Itoa(param[1])
	this.lru[strconv.Itoa(param[1])] = node
	this.cur.Next = node
	this.cur = this.cur.Next
}

func (this *Lru) Del() {
	next := this.head.Next
	delete(this.lru, next.Key)
	this.head.Next.Next.Pre = this.head
	this.head.Next = this.head.Next.Next
}

func getOpt(param []int) int {
	return param[0]
}

func LRU(operators [][]int, k int) []int {
	// write code here
	lru := Lru{}
	lru.lru = make(map[string]*LruNode)
	lru.k = k
	lru.head = &LruNode{
		Next:  nil,
		Value: -1,
	}
	lru.cur = lru.head
	result := make([]int, 0)
	for i := 0; i < len(operators); i++ {
		if getOpt(operators[i]) == Get {
			result = append(result, lru.Get(operators[i]))
			continue
		}
		lru.Set(operators[i])
	}
	return result
}
